Primality Test
   HOME

TheInfoList



OR:

A primality test is an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for determining whether an input number is
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. Among other fields of
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, it is used for
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
. Unlike
integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...
, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its
running time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
is
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
in the size of the input). Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is
composite Composite or compositing may refer to: Materials * Composite material, a material that is made from several different substances ** Metal matrix composite, composed of metal and other parts ** Cermet, a composite of ceramic and metallic materials ...
. Therefore, the latter might more accurately be called ''compositeness tests'' instead of primality tests.


Simple methods

The simplest primality test is ''
trial division Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer ''n'', the integer to be factored, can be divided by each number in turn ...
'': given an input number, ''n'', check whether it is evenly
divisible In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
by any
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
between 2 and (i.e. that the division leaves no
remainder In mathematics, the remainder is the amount "left over" after performing some computation. In arithmetic, the remainder is the integer "left over" after dividing one integer by another to produce an integer quotient ( integer division). In algeb ...
). If so, then ''n'' is
composite Composite or compositing may refer to: Materials * Composite material, a material that is made from several different substances ** Metal matrix composite, composed of metal and other parts ** Cermet, a composite of ceramic and metallic materials ...
. Otherwise, it is
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
.Riesel (1994) pp.2-3 For example, consider the number 100, which is evenly divisible by these numbers: :2, 4, 5, 10, 20, 25, 50 Note that the largest factor, 50, is half of 100. This holds true for all ''n'': all divisors are less than or equal to ''n''/2. Actually, when we test all possible divisors up to ''n''/2, we will discover some factors ''twice''. To observe this, rewrite the list of divisors as a list of products, each equal to 100: : Notice that products past 10 × 10 merely repeat numbers which appeared in earlier products. For example, 5 × 20 and 20 × 5 consist of the same numbers. This holds true for all ''n'': all unique divisors of ''n'' are numbers less than or equal to , so we need not search past that. (In this example, = = 10.) All even numbers greater than 2 can also be eliminated: if an even number can divide ''n'', so can 2. Let's use trial division to test the primality of 17. We need only test for divisors up to , i.e. integers less than or equal to \scriptstyle \sqrt \approx 4.12, namely 2, 3, and 4. We can skip 4 because it is an even number: if 4 could evenly divide 17, 2 would too, and 2 is already in the list. That leaves 2 and 3. We divide 17 with each of these numbers, and we find that neither divides 17 evenly—both divisions leave a remainder. So, 17 is prime. We can improve this method further. Observe that all primes greater than 3 are of the form , where ''k'' is any integer greater than 0. This is because all integers can be expressed as , where ''i'' = −1, 0, 1, 2, 3, or 4. Note that 2 divides and 3 divides . So, a more efficient method is to test whether ''n'' is divisible by 2 or 3, then to check through all numbers of the form \scriptstyle 6k \ \pm \ 1 \leq\sqrt n. This is 3 times faster than testing all numbers up to . Generalising further, all primes greater than ''c''# ( c primorial) are of the form ''c''# · ''k'' + ''i'', for ''i'' < ''c''#, where ''c'' and ''k'' are integers and ''i'' represents the numbers that are
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
to c#. For example, let . Then . All integers are of the form for i in and ''k'' an integer. However, 2 divides 0, 2, 4,..., 28; 3 divides 0, 3, 6, ..., 27; and 5 divides 0, 5, 10, ..., 25. So all prime numbers greater than 30 are of the form for (i.e. for such that ). Note that if ''i'' and 30 were not coprime, then would be divisible by a prime divisor of 30, namely 2, 3, or 5, and would therefore not be prime. In order to match the previous method of allowing for negative i, instead of checking each i from 1 to ''c''#-1 (because 0 and ''c''# are always even), check each i from 1 to , which will be the list of values ''i'' such that all integers are of the form . In this example, for . Note that this list will always include 1 and the set of primes greater than ''c'' but smaller than . Not all numbers which meet the aforementioned conditions are prime. For example, 437 is of the form of ''c''#''k'' + ''i'' for ''c'' = 7, ''c''#=210, ''k''=2, ''i''=17. However, 437 is a composite number equal to 19*23. That is why the numbers of the given form still need to be tested for primality. As , the number of values that can take over a certain range decreases, and so the time to test ''n'' decreases. For this method, it is also necessary to check for divisibility by all primes that are less than ''c''. Observations analogous to the preceding can be applied
recursively Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
, giving the
Sieve of Eratosthenes In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime n ...
. A good way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes up to a certain bound, such as all primes up to 200. (Such a list can be computed with the
Sieve of Eratosthenes In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime n ...
or by an algorithm that tests each incremental ''m'' against all known primes < ). Then, before testing ''n'' for primality with a serious method, ''n'' can first be checked for divisibility by any prime from the list. If it is divisible by any of those numbers then it is composite, and any further tests can be skipped. A simple but very inefficient primality test uses
Wilson's theorem In algebra and number theory, Wilson's theorem states that a natural number ''n'' > 1 is a prime number if and only if the product of all the positive integers less than ''n'' is one less than a multiple of ''n''. That is (using the notations of m ...
, which states that ''p'' is prime if and only if: :(p-1)! \equiv -1\pmod p \, Although this method requires about ''p'' modular multiplications, rendering it impractical, theorems about primes and modular residues form the basis of many more practical methods.


Example code


Python

The following is a simple primality test in
Python Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (pro ...
using the simple optimization mentioned earlier. More sophisticated methods described below are much faster for large ''n''. def is_prime(n: int) -> bool: if n <= 3: return n > 1 if n % 2

0 or n % 3

0: return False limit = int(n**0.5) for i in range(5, limit+1, 6): if n % i

0 or n % (i+2)

0: return False return True


C, C++, C# & D

The following is a primality test in the C family of languages using the same optimization as above. bool IsPrime(int n)


JavaScript

The following is a primality test in
JavaScript JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...
using the same optimization as above. function isPrime(num)


R

The following is a primality test in
R (programming language) R is a programming language for statistical computing and graphics supported by the R Core Team and the R Foundation for Statistical Computing. Created by statisticians Ross Ihaka and Robert Gentleman, R is used among data miners, bioinform ...
using the same optimization as above. is.prime <- function(number)


Dart

The following is a primality test in
Dart (programming_language) Dart is a programming language designed for client development, such as for the web and mobile apps. It is developed by Google and can also be used to build server and desktop applications. It is an object-oriented, class-based, garbage-collec ...
using the same optimization as above. checkIfPrimeNumber(number)


Free Pascal

The following is a primality test in
Free Pascal Free Pascal Compiler (FPC) is a compiler for the closely related programming-language dialects Pascal and Object Pascal. It is free software released under the GNU General Public License, witexception clausesthat allow static linking against its ...
using the same optimization as above. function IsPrime(N:Integer):Boolean; var I:Integer; begin if((N = 2) or (N = 3)) then Exit(True); if((N <= 1) or (N mod 2 = 0) or (N mod 3 = 0)) then Exit(False); I := 5; while(I * I <= N) do begin if((N mod I = 0) or (N mod (I+2) = 0)) then Exit(False); Inc(I, 6); end; Exit(True); end;


Heuristic tests

These are tests that seem to work well in practice, but are unproven and therefore are not, technically speaking, algorithms at all. The Fermat test and the Fibonacci test are simple examples, and they are ''very'' effective when combined.
John Selfridge John Lewis Selfridge (February 17, 1927 – October 31, 2010), was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics. Education Selfridge received his Ph.D. in 195 ...
has conjectured that if ''p'' is an odd number, and ''p'' ≡ ±2 (mod 5), then ''p'' will be prime if both of the following hold: * 2''p''−1 ≡ 1 (mod ''p''), * ''f''''p''+1 ≡ 0 (mod ''p''), where ''fk'' is the ''k''-th
Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
. The first condition is the Fermat primality test using base 2. In general, if ''p'' ≡ a (mod ''x''2+4), where ''a'' is a quadratic non-residue (mod ''x''2+4) then ''p'' should be prime if the following conditions hold: * 2''p''−1 ≡ 1 (mod ''p''), * ''f''(''1'')''p''+1 ≡ 0 (mod ''p''), ''f''(''x'')''k'' is the ''k''-th
Fibonacci polynomial In mathematics, the Fibonacci polynomials are a polynomial sequence which can be considered as a generalization of the Fibonacci numbers. The polynomials generated in a similar way from the Lucas numbers are called Lucas polynomials. Definition The ...
at ''x''. Selfridge,
Carl Pomerance Carl Bernard Pomerance (born 1944 in Joplin, Missouri) is an American number theorist. He attended college at Brown University and later received his Ph.D. from Harvard University in 1972 with a dissertation proving that any odd perfect number ...
, and Samuel Wagstaff together offer $620 for a counterexample. The problem is still open as of September 11, 2015.


Probabilistic tests

Probabilistic tests are more rigorous than heuristics in that they provide provable bounds on the probability of being fooled by a composite number. Many popular primality tests are probabilistic tests. These tests use, apart from the tested number ''n'', some other numbers ''a'' which are chosen at random from some
sample space In probability theory, the sample space (also called sample description space, possibility space, or outcome space) of an experiment or random trial is the set of all possible outcomes or results of that experiment. A sample space is usually den ...
; the usual randomized primality tests never report a prime number as composite, but it is possible for a composite number to be reported as prime. The probability of error can be reduced by repeating the test with several independently chosen values of ''a''; for two commonly used tests, for ''any'' composite ''n'' at least half the ''a''s detect ''n''s compositeness, so ''k'' repetitions reduce the error probability to at most 2−''k'', which can be made arbitrarily small by increasing ''k''. The basic structure of randomized primality tests is as follows: #Randomly pick a number ''a''. #Check equality (corresponding to the chosen test) involving ''a'' and the given number ''n''. If the equality fails to hold true, then ''n'' is a composite number and ''a'' is a ''witness'' for the compositeness, and the test stops. #Get back to the step one until the required accuracy is reached. After one or more iterations, if ''n'' is not found to be a composite number, then it can be declared probably prime.


Fermat primality test

The simplest probabilistic primality test is the
Fermat primality test The Fermat primality test is a probabilistic test to determine whether a number is a probable prime. Concept Fermat's little theorem states that if ''p'' is prime and ''a'' is not divisible by ''p'', then :a^ \equiv 1 \pmod. If one wants to tes ...
(actually a compositeness test). It works as follows: :Given an integer ''n'', choose some integer ''a'' coprime to ''n'' and calculate ''an'' − 1 modulo ''n''. If the result is different from 1, then ''n'' is composite. If it is 1, then ''n'' may be prime. If ''an''−1 (modulo ''n'') is 1 but ''n'' is not prime, then ''n'' is called a
pseudoprime A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy. Some sources use the term pseudoprime to ...
to base ''a''. In practice, we observe that, if ''an''−1 (modulo ''n'') is 1, then ''n'' is usually prime. But here is a counterexample: if ''n'' = 341 and ''a'' = 2, then : 2^ \equiv 1\pmod even though 341 = 11·31 is composite. In fact, 341 is the smallest pseudoprime base 2 (see Figure 1 of ). There are only 21853 pseudoprimes base 2 that are less than 2.5 (see page 1005 of ). This means that, for ''n'' up to 2.5, if ''2n''−1 (modulo ''n'') equals 1, then ''n'' is prime, unless ''n'' is one of these 21853 pseudoprimes. Some composite numbers (
Carmichael number In number theory, a Carmichael number is a composite number n, which in modular arithmetic satisfies the congruence relation: :b^n\equiv b\pmod for all integers b. The relation may also be expressed in the form: :b^\equiv 1\pmod. for all integers ...
s) have the property that ''an'' − 1 is 1 (modulo ''n'') for every ''a'' that is coprime to ''n''. The smallest example is ''n'' = 561 = 3·11·17, for which ''a560'' is 1 (modulo 561) for all ''a'' coprime to 561. Nevertheless, the Fermat test is often used if a rapid screening of numbers is needed, for instance in the key generation phase of the RSA public key cryptographic algorithm.


Miller–Rabin and Solovay–Strassen primality test

The
Miller–Rabin primality test The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen prim ...
and
Solovay–Strassen primality test The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 196 ...
are more sophisticated variants, which detect all composites (once again, this means: for ''every'' composite number ''n'', at least 3/4 (Miller–Rabin) or 1/2 (Solovay–Strassen) of numbers ''a'' are witnesses of compositeness of ''n''). These are also compositeness tests. The Miller–Rabin primality test works as follows: Given an integer ''n'', choose some positive integer ''a'' < ''n''. Let 2''s''''d'' = ''n'' − 1, where ''d'' is odd. If : a^ \not\equiv \pm 1\pmod and : a^ \not\equiv -1\pmod for all 0 \le r \le s - 1, then ''n'' is composite and ''a'' is a witness for the compositeness. Otherwise, ''n'' may or may not be prime. The Miller–Rabin test is a
strong pseudoprime A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes". Unlike the Fermat pseudoprimes, for which there ex ...
test (see PSW page 1004). The Solovay–Strassen primality test uses another equality: Given an odd number ''n'', choose some integer ''a'' < ''n'', if : a^ \not\equiv \left(\frac\right) \pmod n, where \left(\frac\right) is the
Jacobi symbol Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...
, then ''n'' is composite and ''a'' is a witness for the compositeness. Otherwise, ''n'' may or may not be prime. The Solovay–Strassen test is an
Euler pseudoprime In arithmetic, an odd composite integer ''n'' is called an Euler pseudoprime to base ''a'', if ''a'' and ''n'' are coprime, and : a^ \equiv \pm 1\pmod (where ''mod'' refers to the modulo operation). The motivation for this definition is the f ...
test (see PSW page 1003). For each individual value of ''a'', the Solovay–Strassen test is weaker than the Miller–Rabin test. For example, if ''n'' = 1905 and ''a'' = 2, then the Miller-Rabin test shows that ''n'' is composite, but the Solovay–Strassen test does not. This is because 1905 is an Euler pseudoprime base 2 but not a strong pseudoprime base 2 (this is illustrated in Figure 1 of PSW).


Frobenius primality test

The Miller–Rabin and the Solovay–Strassen primality tests are simple and are much faster than other general primality tests. One method of improving efficiency further in some cases is the Frobenius pseudoprimality test; a round of this test takes about three times as long as a round of Miller–Rabin, but achieves a probability bound comparable to seven rounds of Miller–Rabin. The Frobenius test is a generalization of the
Lucas pseudoprime Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence. Baillie-Wagstaff-Lucas pseudoprimes Baill ...
test.


Baillie–PSW primality test

The Baillie–PSW primality test is a probabilistic primality test that combines a Fermat or Miller–Rabin test with a Lucas probable prime test to get a primality test that has no known counterexamples. That is, there are no known composite ''n'' for which this test reports that ''n'' is probably prime. It has been shown that there are no counterexamples for ''n'' < 2^.


Other tests

Leonard Adleman Leonard Adleman (born December 31, 1945) is an American computer scientist. He is one of the creators of the RSA encryption algorithm, for which he received the 2002 Turing Award, often called the Nobel prize of Computer science. He is also kno ...
and Ming-Deh Huang presented an errorless (but expected polynomial-time) variant of the elliptic curve primality test. Unlike the other probabilistic tests, this algorithm produces a
primality certificate In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or u ...
, and thus can be used to prove that a number is prime. The algorithm is prohibitively slow in practice. If
quantum computer Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
s were available, primality could be tested asymptotically faster than by using classical computers. A combination of
Shor's algorithm Shor's algorithm is a quantum algorithm, quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N , Shor's algorithm ...
, an integer factorization method, with the
Pocklington primality test In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer. The test uses a partial factorization of N - 1 to prove that an integer N is prime. It produces a prim ...
could solve the problem in O((\log n)^3 (\log\log n)^2 \log\log\log n).


Fast deterministic tests

Near the beginning of the 20th century, it was shown that a corollary of Fermat's little theorem could be used to test for primality. This resulted in the
Pocklington primality test In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer. The test uses a partial factorization of N - 1 to prove that an integer N is prime. It produces a prim ...
. However, as this test requires a partial
factorization In mathematics, factorization (or factorisation, see American and British English spelling differences#-ise, -ize (-isation, -ization), English spelling differences) or factoring consists of writing a number or another mathematical object as a p ...
of ''n'' − 1 the running time was still quite slow in the worst case. The first deterministic primality test significantly faster than the naive methods was the cyclotomy test; its runtime can be proven to be O((log ''n'')''c'' log log log ''n''), where ''n'' is the number to test for primality and ''c'' is a constant independent of ''n''. Many further improvements were made, but none could be proven to have polynomial running time. (Note that running time is measured in terms of the size of the input, which in this case is ~ log ''n'', that being the number of bits needed to represent the number ''n''.) The elliptic curve primality test can be proven to run in O((log ''n'')6), if some conjectures on
analytic number theory In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Diric ...
are true. Similarly, under the
generalized Riemann hypothesis The Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmetical objects can be described by so-called global ''L''-functions, whic ...
, the deterministic Miller's test, which forms the basis of the probabilistic Miller–Rabin test, can be proved to run in Õ((log ''n'')4). In practice, this algorithm is slower than the other two for sizes of numbers that can be dealt with at all. Because the implementation of these two methods is rather difficult and creates a risk of programming errors, slower but simpler tests are often preferred. In 2002, the first provably unconditional deterministic polynomial time test for primality was invented by
Manindra Agrawal Manindra Agrawal (born 20 May 1966) is a professor at the Department of Computer Science and Engineering and the Deputy Director at the Indian Institute of Technology, Kanpur. He was also the recipient of the first Infosys Prize for Mathematics ...
,
Neeraj Kayal Neeraj Kayal ( hi, नीरज कयाल) is an Indian computer scientist and mathematician noted for development of the AKS primality test, along with Manindra Agrawal and Nitin Saxena. Kayal was born and raised in Guwahati, India. Earl ...
, and
Nitin Saxena Nitin Saxena (born 3 May 1981Saxena's CV at University of Bonn
) is ...
. The
AKS primality test The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic Determinism is a philosophical view, where all events are determined completely by previously existing causes. Determi ...
runs in Õ((log ''n'')12) (improved to Õ((log ''n'')7.5) in the published revision of their paper), which can be further reduced to Õ((log ''n'')6) if the Sophie Germain conjecture is true. Subsequently, Lenstra and Pomerance presented a version of the test which runs in time Õ((log ''n'')6) unconditionally. Agrawal, Kayal and Saxena suggest a variant of their algorithm which would run in Õ((log ''n'')3) if
Agrawal's conjecture In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test. Agrawal's conjecture states formally: Let n and r be two coprime integers, coprime positive integers. If :(X - 1)^n \equiv X^n - ...
is true; however, a heuristic argument by Hendrik Lenstra and Carl Pomerance suggests that it is probably false. A modified version of the Agrawal's conjecture, the Agrawal–Popovych conjecture, may still be true.


Complexity

In
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, the formal language corresponding to the prime numbers is denoted as PRIMES. It is easy to show that PRIMES is in
Co-NP In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...
: its complement COMPOSITES is in NP because one can decide compositeness by nondeterministically guessing a factor. In 1975,
Vaughan Pratt Vaughan Pratt (born April 12, 1944) is a Professor Emeritus at Stanford University, who was an early pioneer in the field of computer science. Since 1969, Pratt has made several contributions to foundational areas such as search algorithms, sorti ...
showed that there existed a certificate for primality that was checkable in polynomial time, and thus that PRIMES was in NP, and therefore in NP ∩ coNP. See
primality certificate In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or u ...
for details. The subsequent discovery of the Solovay–Strassen and Miller–Rabin algorithms put PRIMES in
coRP Corp may refer to: Surname *Aaron Corp (born 1989), American football quarterback * Brandon Corp (born 1987), American lacrosse player *Ronald Corp (born 1951), English composer, conductor and Church of England priest Abbreviation *Corp., an abbre ...
. In 1992, the Adleman–Huang algorithm reduced the complexity to ZPP = RP ∩ coRP, which superseded Pratt's result. The
Adleman–Pomerance–Rumely primality test In computational number theory, the Adleman–Pomerance–Rumely primality test is an algorithm for determining whether a number is prime. Unlike other, more efficient algorithms for this purpose, it avoids the use of random numbers, so it is a dete ...
from 1983 put PRIMES in QP (
quasi-polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
), which is not known to be comparable with the classes mentioned above. Because of its tractability in practice, polynomial-time algorithms assuming the Riemann hypothesis, and other similar evidence, it was long suspected but not proven that primality could be solved in polynomial time. The existence of the
AKS primality test The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic Determinism is a philosophical view, where all events are determined completely by previously existing causes. Determi ...
finally settled this long-standing question and placed PRIMES in P. However, PRIMES is not known to be
P-complete In computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction. The notion of P-complete decision problems is usef ...
, and it is not known whether it lies in classes lying inside P such as NC or L. It is known that PRIMES is not in AC0.E. Allender, M. Saks, and I.E. Shparlinski, A lower bound for primality, ''J. Comp. Syst. Sci.'' 62 (2001), pp. 356–366.


Number-theoretic methods

Certain number-theoretic methods exist for testing whether a number is prime, such as the Lucas test and Proth's test. These tests typically require factorization of ''n'' + 1, ''n'' − 1, or a similar quantity, which means that they are not useful for general-purpose primality testing, but they are often quite powerful when the tested number ''n'' is known to have a special form. The Lucas test relies on the fact that the
multiplicative order In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n. In other words, the multiplicative order ...
of a number ''a'' modulo ''n'' is ''n'' − 1 for a prime ''n'' when ''a'' is a primitive root modulo n. If we can show ''a'' is primitive for ''n'', we can show ''n'' is prime.


References


Sources

* Chapter 3: Recognizing Primes and Composites, pp. 109–158. Chapter 4: Primality Proving, pp. 159–190. Section 7.6: Elliptic curve primality proving (ECPP), pp. 334–340. * * * *


External links

* – Implementation of the Solovay-Strassen primality test in Maple
Distinguishing prime numbers from composite numbers, by D.J. Bernstein (cr.yp.to)The Prime Pages (primes.utm.edu)
*
PRIMABOINCA
is a research project that uses Internet-connected computers to search for a
counterexample A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "John Smith is not a lazy student" is a ...
to some conjectures. The first conjecture (
Agrawal's conjecture In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test. Agrawal's conjecture states formally: Let n and r be two coprime integers, coprime positive integers. If :(X - 1)^n \equiv X^n - ...
) was the basis for the formulation of the first deterministic prime test algorithm in polynomial time (
AKS algorithm The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists a ...
). {{DEFAULTSORT:Primality Test * Asymmetric-key algorithms